/*
 * Cr�� le 21 mars 06
 */
package fr.cdesire.sudoku.elements;

import fr.cdesire.sudoku.elements.exceptions.NotSudokuSolutionException;
import fr.cdesire.sudoku.elements.exceptions.NotSudokuSolutionException;
import fr.cdesire.sudoku.elements.exceptions.NotValidSudokuGridException;
import fr.cdesire.sudoku.elements.exceptions.NotValidSudokuGridException;
import fr.cdesire.sudoku.utils.ArbreEtats;
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;
import java.util.Stack;
import java.util.TreeSet;

/**
 * @author Cedric
 */
public class Sudoku {
	
	/**
	 * Nombre de cases pour un c�t� d'une r�gion de Sudoku.
	 */
	public static final int NB_CASES_LIGNE_REGION = 3;
	/**
	 * Nombre de cases pour un c�t� d'une grille de Sudoku.
	 */
	public static final int NB_CASES_LIGNE_GRILLE = 9;
	
	private static ArbreEtats arbre = new ArbreEtats();
	
	private SortedSet casesVides;
	private List casesPleines;
	private int[][] grille;
	
	// Recherche l'index de la r�gion correspondante aux coordonn�es
	// pass�es en param�tres.
	private static int posRegion(int posLigne, int posCol) {
		return (posLigne/NB_CASES_LIGNE_REGION) * NB_CASES_LIGNE_REGION + posCol/NB_CASES_LIGNE_REGION;
	}
	
	// Recherche l'index d'une valeur dans une r�gion correspondante
	// aux coordonn�es pass�es en param�tres.	
	private static int posValDansRegion(int posLigne, int posCol) {
		return (posLigne%NB_CASES_LIGNE_REGION) * NB_CASES_LIGNE_REGION + posCol%NB_CASES_LIGNE_REGION;
	}
	
	/**
	 * M�thode statique r�cursive de recherche d'une solution de
	 * Sudoku.
	 * @param sudoku Sudoku source.
	 * @return Solution de Sudoku.
	 * @throws NotSudokuSolutionException Solution inexistante.
	 */
	public static Sudoku rechercheSolution(Sudoku sudoku) 
		throws NotSudokuSolutionException {
		
		if (sudoku.casesVides.isEmpty()) return sudoku;
		
		Stack sudokusPossibles = new Stack();
		Case caseVide = (Case)sudoku.getCasesVides().first();
		Iterator iter = caseVide.getPossibilites().iterator();
		
		while(iter.hasNext()) {
			
			int[][] grille = new int[NB_CASES_LIGNE_GRILLE][NB_CASES_LIGNE_GRILLE];
		 
			for (int i=0; i<NB_CASES_LIGNE_GRILLE; i++) {
				for (int j=0; j<NB_CASES_LIGNE_GRILLE; j++) {
					grille[i][j] = sudoku.getGrille()[i][j];
				}
			}
			grille[caseVide.getPosLigne()][caseVide.getPosColonne()] = ((Integer)iter.next()).intValue();
			sudokusPossibles.push(new Sudoku(grille));
		}
		
		try {
			return rechercheSolution((Sudoku)arbre.getEtat(sudokusPossibles));
		} catch (EmptyStackException e) {
			throw new NotSudokuSolutionException("Il n'existe pas de solutions possibles");
		}
	}
	
	/**
	 * Appel du constructeur de Sudoku.
	 * @param grille Grille des valeurs du Sudoku (par ligne, puis 
	 * par colonne).
	 */
	public Sudoku(int[][] grille) {
		
		this.grille = grille;
		
		casesVides = new TreeSet();
		casesPleines = new ArrayList();
		
		// R�organisation de la grille sous forme de tableau de
		// lignes, tableau de colonnes, tableau de r�gions.
		ArrayList lignes = new ArrayList();
		ArrayList colonnes = new ArrayList();
		ArrayList regions = new ArrayList();
		
		for (int i=0; i<NB_CASES_LIGNE_GRILLE; i++) {
			
			ArrayList ligne = new ArrayList();
			ArrayList colonne = new ArrayList();
			ArrayList region = new ArrayList();
				
			for (int j=0; j<NB_CASES_LIGNE_GRILLE; j++) {
					
				ligne.add(new Integer(this.grille[i][j]));
				colonne.add(new Integer(this.grille[j][i]));
				region.add(new Integer(this.grille[posRegion(i,j)][posValDansRegion(i,j)]));	
			}
			
			lignes.add(ligne);
			colonnes.add(colonne);
			regions.add(region);
		}
		
		// Cr�ation des cases et alimentation des tableaux 
		// casesPleines et casesVides.
		for (int i=0; i<NB_CASES_LIGNE_GRILLE; i++) {
			for (int j=0; j<NB_CASES_LIGNE_GRILLE; j++) {
				Case caseSudoku = new Case(i,j,grille[i][j],(ArrayList)lignes.get(i),(ArrayList)colonnes.get(j),(ArrayList)regions.get(posRegion(i,j)));
				if (caseSudoku.isVide()) casesVides.add(caseSudoku);
				else casesPleines.add(caseSudoku);
			}
		}	 
	}
	
	/**
	 * Valide la grille de Sudoku sinon l�ve une exception en 
	 * indiquant les cases non valides.
	 * @throws NotValidSudokuGridException Grille non valide.
	 */
	public void validation() 
		throws NotValidSudokuGridException {
		
		for (int i = 0; i < casesPleines.size() - 1; i++) {
			
			Case case1 = (Case)casesPleines.get(i);
			
			for (int j = i+1; j < casesPleines.size(); j++) {
				
				Case case2 = (Case)casesPleines.get(j);
				
				if (case1.getValeur() == case2.getValeur()) {
					
					if (case1.getPosLigne() == case2.getPosLigne()){
						throw new NotValidSudokuGridException(
							"Ligne " + (case1.getPosLigne() + 1) + " invalide aux colonnes " + 
							(case1.getPosColonne() + 1) + " et " + (case2.getPosColonne() + 1));
					}
					
					if (case1.getPosColonne() == case2.getPosColonne()){
						throw new NotValidSudokuGridException(
							"Colonne " + (case1.getPosColonne() + 1) + " invalide aux lignes " + 
							(case1.getPosLigne() + 1) + " et " + (case2.getPosLigne() + 1));
					}
					
					if (posRegion(case1.getPosLigne(), case1.getPosColonne()) == posRegion(case2.getPosLigne(), case2.getPosColonne())){
						throw new NotValidSudokuGridException(
							"Region invalide en (" + (case1.getPosLigne() + 1) + ", " + 
							(case1.getPosColonne() + 1) + ") et (" + (case2.getPosLigne() + 1) + ", " +
							(case2.getPosColonne() + 1) + ")");
					}
				}	
			}
		}
	}
	
	/**
	 * @return Grille du Sudoku.
	 */
	public int[][] getGrille() {
		return this.grille;
	}
	
	/**
	 * @return Cases vides du Sudoku.
	 */
	public SortedSet getCasesVides() {
		return this.casesVides;
	}
}
